1. Field of the Invention
This invention relates to a packet identification device and a packet identification method for identifying the contents of a packet, and more particularly to a packet identification device and a packet identification method that identify a packet by comparison with data registered in advance.
2. Description of the Related Art
As a basic function of processing packets transferred via an IP (Internet Protocol) network, there has been conventionally known a function of identifying each packet based on an IP address, a TCP (Transmission Control Protocol) port number, or the like. For example, in routing packets using a router, the interface of a next transfer destination is determined based on a destination IP address. Further, in the case of NAT (Network Address Translation), a router performs conversion of an IP address and a port number based on destination and source IP addresses and destination and source TCP port numbers.
Further, when a VPN (Virtual Private Network) device decrypts encrypted packets, a packet identification device of the VPN device compares pre-registered information (hereinafter referred to as the lookup table) with the contents of a packet currently being processed.
FIG. 20 is a diagram showing an example of the data structure of a conventional lookup table. In the lookup table 910, there are registered SA IDs, Src IP addresses, Dst IP addresses, and SPIs (Security Parameter Indexes). It should be noted that SA ID represents an identifier of an SA (Security Association), Src IP address represents a source IP address, and Dst IP address represents a destination IP address.
The packet identification device performs comparison between records of the lookup table 910 configured as above and a set of pieces of information to be compared (destination IP address, source IP address, and SPI) contained in a packet, and identifies an SA based on the SA ID of a record matching the information. The VPN device selects an appropriate secret key based on the SA and performs decryption.
FIG. 21 is a flowchart of a conventional packet identification process. In the following, the process shown in FIG. 21 will be described in the order of step numbers.
[Step S91] The packet identification device sets a variable i to 0.
[Step S92] The packet identification device determines whether or not an i-th record of the lookup table 910 is valid. If the i-th record is valid, the process proceeds to a step S93, whereas if the i-th record is not valid, the process proceeds to a step S96.
[Step S93] The packet identification device compares the source IP address, destination IP address, and SPI in an ESP header of the i-th record of the lookup table 910 with those of a packet, respectively.
[Step S94] The packet identification device determines, based on the result of the comparison in the step S93, whether there is a match in all the compared data items between the i-th record and the packet. If there is a match in all the compared data items, the process proceeds to a step S95. If there is any mismatch, the process proceeds to the step S96.
[Step S95] The packet identification device outputs information indicative of the match between the i-th record and the packet, followed by terminating the present process.
[Step S96] The packet identification device increments the variable i by 1.
[Step S97] The packet identification device determines whether or not the variable i is larger than the number of records registered in the lookup table 910. If the variable i is larger than the number of the registered records, the process proceeds to a step S98, whereas if the variable i is equal to or smaller than the number of the registered records, the process returns to the step S92.
[Step S98] The packet identification device outputs information indicative of a mismatch between the all the records and the packet, followed by terminating the present process.
As described above, in the prior art, the SA of a received packet is identified by a program sequentially comparing a set of a destination IP address, a source IP address, and an SPI in the ESP header of the received packet with all entries in a lookup table.
Further, in routing packets, a comparison is performed between 32-bit values indicative of respective destination IP addresses. Further, in performing NAT, a comparison is performed between data values each defined by a total of 96 bits which indicate destination and source IP addresses and destination and source TCP port numbers.
It should be noted that in FIG. 21, to search the lookup table, there is employed a simplest method, i.e. to search the lookup table in the order of SA numbers. Besides this method, there are various algorithms for efficient search, but they are no different in that a received packet and only one record of registered data are compared in one comparison process. Therefore, with an increase in the number of registered data, search time is inevitably increased.
The comparison is generally handled by software, and places a heavy load on software processing. Therefore, it is predicted that the processing for the comparison will more often cause a bottleneck in the speed-up of network operation in the future. Further, when IPv6 comes into wide use in which one destination IP address is represented by 128 bits, the amount of data for comparison will dramatically increase, resulting in a further increased load on the software processing.
Data comparison can be handled not only by software but also by hardware (see e.g. Japanese Unexamined Patent Publication (Kokai) No. H04-109337). The hardware capable of data comparison includes a CAM (Content Addressable Memory). The use of a CAM makes it possible to identify each packet at high speed. However, if the amount of data to be stored for comparison is large, it is required to use a large-capacity CAM. The problem here is that the usage of a CAM is complicated, and in addition, an increased number of pins are needed so as to compare the large amount of data in a single operation. For this reason, it is extremely difficult in terms of design to install a large-capacity CAM. Moreover, CAMs are very expensive, and hence for economical reasons, it is often difficult to increase the capacity of CAMs. As is apparent from the above, the idea of increasing the capacity of a CAM is impractical.
It is necessary to compare a large amount of data when executing highly developed packet filtering, packet encryption/decryption, etc. A technique has also been contemplated to enable a router to achieve highly developed packet filtering without increasing the capacity of a CAM.
For example, a CAM has been proposed which is capable of performing high-speed comparison of a plurality of pieces of information (e.g. a MAC address and an IP address) contained in a packet, using a plurality of determination circuits each including a comparison circuit with a masking function (see e.g. Japanese Unexamined Patent Publication (Kokai) No. H 07-143156). In this technique, when data to be compared is input, masking is applied to the contents of a database register according to mask data, and then a comparison is performed between unmasked bits and the corresponding bits of the input data.
Thus, data transfer involving IP address and MAC address comparisons can be performed using a single CAM. For example, filtering is executed using predetermined bits of IP addresses, and when it is determined that a packet is not for the IP address filtering, a MAC address comparison is executed to thereby select the interface of an output destination.
In a CAM of the type disclosed in Japanese Unexamined Patent Publication (Kokai) No. H 04-109337, to avoid an increase in the capacity of the CAM, one of an IP address, a MAC address, and other data items for comparison is stored in a database register. Therefore, when data to be compared (hereinafter referred to as “comparison data”) is switched (e.g. from an IP address to a MAC address), rewriting of the database register and a database mask register occurs, which reduces processing speed.
Moreover, according to the invention disclosed in the aforementioned Patent Publication, processing for masking and comparison is carried out in units corresponding to the data length of one entry storable in the database register. Therefore, it is necessary to use comparison circuits or the like capable of comparing bits corresponding to the data width of one entry. In this case, if a database register large enough to store all data items (such as IP addresses, MAC addresses, etc.) for use in comparison is provided, the size of the comparison circuit will be increased, which causes an increase in the manufacturing costs of the CAM.